package com.zhugang.week10;

/**
 * @program algorithms
 * @description: bages2DP
 * @author: chanzhugang
 * @create: 2022/08/28 21:15
 */
public class Bages2ByDP {

    /**
     * 二维费用背包问题
     * 动态规划解法
     *
     * @param weight
     * @param value
     * @param n
     * @param w
     * @return
     */
    public int knapsack(int[] weight, int[] value, int n, int w) {
        // 初始化为最小值
        int[][] dp = new int[n][w + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                dp[i][j] = Integer.MIN_VALUE;
            }
        }

        // 初始化第一行
        dp[0][0] = 0;
        if (weight[0] <= w) {
            dp[0][weight[0]] = value[0];
        }
        // 第一种动态转移方程
        /*for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                if (dp[i - 1][j] == Integer.MIN_VALUE) {
                    continue;
                }
                // 不装
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                if (j + weight[i] <= w) {
                    // 装
                    dp[i][j + weight[i]] = Math.max(dp[i][j + weight[i]], dp[i - 1][j] + value[i]);
                }
            }
        }*/
        // 第二种动态转移方程：推荐(逆推)
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                if (dp[i - 1][j] != Integer.MIN_VALUE) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                }
                if (j - weight[i] >= 0 && dp[i - 1][j - weight[i]] != Integer.MIN_VALUE) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }

        }

        int res = Integer.MIN_VALUE;
        for (int j = 0; j <= w; j++) {
            res = Math.max(res, dp[n - 1][j]);

            /*if (res < dp[n - 1][j]) {
                res = dp[n - 1][j];
            }*/
        }
        return res;
    }
}